package leecode.array.数组其他问题;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author wangxi created on 2021/6/6 22:25
 * @version v1.0
 *
 * https://leetcode-cn.com/problems/subarray-sum-equals-k/
 *
 * 给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
 *
 *
 * 前缀和
 */
public class SubarraySumEqualsK {


    public static void main(String[] args) {
        SubarraySumEqualsK obj = new SubarraySumEqualsK();
        int[] nums = {1,2,3,2,2};

        int res = obj.subarraySum(nums, 4);
        System.out.println(res);

        int[][] aa = new int[1][1];
        Arrays.sort(aa, (o1, o2) -> {
            return o1[0] - o2[0];
        });


    }


    /**
     * 利用前缀和的思想，这个思想的前提是初始化 sum = 0的key-val元素
     *
     * 和两数之和的思想很相近
     *
     * 下标 A, B, C
     *
     * 下标 A ~ B的和记为sum1
     * 下标 A ~ C的和记为sum2
     * 如果 sum2 - k 作为key == sum1说明，B ~ C区间即为和为k的子数组
     */
    public int subarraySum(int[] nums, int k) {
        // key：前缀和，value：key 对应的前缀和的个数
        Map<Integer, Integer> preSumFreq = new HashMap<>();
        // 对于下标为 0 的元素，前缀和为 0，个数为 1
        preSumFreq.put(0, 1);

        int preSum = 0;
        int count = 0;
        for (int num : nums) {
            preSum += num;

            // 先获得前缀和为 preSum - k 的个数，加到计数变量里
            if (preSumFreq.containsKey(preSum - k)) {
                count += preSumFreq.get(preSum - k);
            }

            // 然后维护 preSumFreq 的定义
            // 需要考虑负数的情况
            preSumFreq.put(preSum, preSumFreq.getOrDefault(preSum, 0) + 1);
        }
        return count;
    }
}
